﻿#pragma once
#include <iostream>
#include <thread>
#include <vector>
#include <unordered_map>
#include <cassert>
#include <mutex>

using std::cout;
using std::endl;

//ThreadCache能申请的最大对象为256KB
static const size_t MAX_BYTES = 256 * 1024;

// thread cache 和central cache⾃由链表哈希桶的表⼤⼩
static const size_t NFREELISTS = 208;

//PageCache哈希表大小
static const size_t NPAGES = 129;
//一页8kb, 就是8*1024byte，就是 1 << 13
static const size_t PAGE_SHIFT = 13;

#ifdef _WIN32
#include <Windows.h>
#else
//其他
#endif

// 直接去堆上按⻚申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等

#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等

#endif
}

#if _WIN64
typedef size_t PAGE_ID;
#elif _WIN32
typedef unsigned long long PAGE_ID;
#endif

static void*& NextObj(void* obj)
{
	return *(void**)obj;
}
class freeList
{
public:
	void push(void* obj)
	{
		//头插
		assert(obj);
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;

		_size += n;

		//void* cur = start;
		//int j = 0;
		//while (cur)
		//{
		//	cur = NextObj(cur);
		//	++j;
		//}
		//if (j < n)
		//{
		//	int x = 0;
		//}
	}
	void* pop()
	{
		//头删+返回删除元素的地址
		assert(_freeList);
		void* obj = _freeList;
		_freeList = NextObj(obj);
		_size--;
		return obj;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);
		start = end = _freeList;
		//条件断电
		void* cur = start;
		int j = 0;
		while (cur)
		{
			cur = NextObj(cur);
			++j;
		}
		if (j < n)
		{
			int x = 0;
		}
		for (size_t i = 1; i < n; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
    bool Empty()
    {
        return _freeList == nullptr;
    }
	//辅助控制一次向CentralCache多少个对象，实现慢增长
	size_t& MaxSize()
	{
		return _maxSize;
	}
	inline size_t Size()const
	{
		return _size;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;//表示该自由链表中有多少个节点
};


//管理对⻬和映射等关系
class ClassSize
{
public:
	//整体控制在最多10%左右的内碎⽚浪费
		// [1,128]                 8byte对⻬        freelist[0, 16)      
		// [128+1,1024]            16byte对⻬       freelist[16, 72)
		// [1024+1,81024]          128byte对⻬      freelist[72, 128)
		// [8*1024+1,641024]       1024byte对⻬     freelist[128, 184)
		// [64*1024+1,256*1024]    8*1024byte对⻬   freelist[184, 208)
	static inline size_t _RoundUp(size_t bytes, size_t align)//抄袭高手的代码
	{
		return (bytes + (align - 1)) & ~(align - 1);
	}
	static inline size_t RoundUp(size_t size)
	{
		//assert(size <= MAX_BYTES);
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8*1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	static inline size_t _Index(size_t bytes, size_t align_shift)//抄袭高手的代码
	{
		return ((bytes + (static_cast<unsigned long long>(1) << align_shift) - 1) >> align_shift) - 1;
	}

	static inline size_t Index(size_t size)//计算映射到哪个哈希桶
	{
		assert(size <= MAX_BYTES);
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size, 4);
		}
		else if (size <= 8 * 1024)
		{
			return _Index(size, 7);
		}
		else if (size <= 64 * 1024)
		{
			return _Index(size, 10);
		}
		else if (size <= 256 * 1024)
		{
			return _Index(size, 13);
		}
		else return -1;
	}
	//控制一次向CentralCache多少个对象
	static inline size_t NumMoveSize(size_t size)
	{
		if (size == 0) return 0;
		size_t n = MAX_BYTES / size;
		if (n < 2) n = 2;
		if (n > 512) n = 512;
		return n;
	}

	// 计算⼀次向系统获取⼏个⻚
	static inline size_t NumMovePage(size_t size)
	{
		size_t n = NumMoveSize(size);//根据对象大小算出所要对象的个数（非真实，只是一个上下限控制的个数）
		size_t npage = n * size;//对象大小乘个数就是需要的内存字节数
		npage >>= PAGE_SHIFT;
		if (npage == 0) npage = 1;//至少是一页
		return npage;
	}
};



struct Span
{
	PAGE_ID _pageId = 0;// 页号，页号由申请空间的地址得来，可以通过页号反推地址
	size_t _n = 0;//该span管理的空间的页数

	//维持双向带头链表结构
	Span* _next = nullptr;
	Span* _prev = nullptr;

	void* _freeList = nullptr;  // 切好的⼩块内存的⾃由链表
	size_t _useCount = 0; //切好⼩块内存，被分配给thread cache的计数

	bool _isUse = false;//标识当前span是否正在被使用
	size_t _objSize = 0;//表示切分好的单个对象大小
};
//双向带头链表结构

class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		//_head = _objPool.New();
		_head->_next = _head;
		_head->_prev = _head;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	void PushFront(Span* NewSpan)
	{
		Insert(Begin(), NewSpan);
	}
	void Insert(Span* pos, Span* NewSpan)
	{
		assert(pos);
		assert(NewSpan);

		Span* prev = pos->_prev;
		prev->_next = NewSpan;
		NewSpan->_prev = prev;
		NewSpan->_next = pos;
		pos->_prev = NewSpan;
	}
	Span* PopFront()
	{
		Span* front = Begin();
		Erase(front);
		return front;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;
	}
	bool Empty()
	{
		return _head == _head->_next;
	}

private:
	Span* _head;
public:
	std::mutex _mtx;//桶锁
};